#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""


解法完全是自己想出来的: 王鹤! (用了单调栈的特性)

https://blog.csdn.net/Asun0204/article/details/81606180

两个长度为n的序列a, b，问有多少个区间[l,r]满足如下式子：
max(a[l,r])<min(b[l,r]),0≤l≤r<nmax(a[l,r])<min(b[l,r]),0≤l≤r<n
即a区间的最大值小于b区间的最小值。
数值范围： n<1e5, aibi<1e9

输入描述
第一行一个整数n
第二行n个数，第i个为ai
第三行n个数，第i个为bi
1
2
3
输出描述
一行一个整数，表示答案
1
示例
输入
3
3 3 3       up (up 最小大于down最大)
3 2 1       down
"""

import random


def binary_find_max_min(array, num, lessor, extractor):
    # 从array中找到小于num的, 最大的索引
    left, right = 0, len(array)-1

    while right - left > 1:
        mid = (right + left) // 2
        mid_num = extractor(mid)
        if lessor(mid_num, num):
            # num > mid_num
            left = mid
        else:
            right = mid - 1

    assert right - left == 0 or right - left == 1
    for i in range(left, right+1):
        mid_num = extractor(i)
        # if mid_num >= num:
        if not lessor(mid_num, num):
            return i-1

    return right

def test_binary_s():
    a = [3 , 5, 7, 9]
    num = 6

    def lessor(a, b):
        return a < b

    def extractor(idx):
        return a[idx]

    ret = binary_find_max_min(a, 6, lessor, extractor)
    assert ret == 1

    ret = binary_find_max_min(a, 5, lessor, extractor)
    assert ret == 0

    ret = binary_find_max_min(a, 3, lessor, extractor)
    assert ret == -1

    ret = binary_find_max_min(a, 2, lessor, extractor)
    assert ret == -1

    ret = binary_find_max_min(a, 7, lessor, extractor)
    assert ret == 1

    ret = binary_find_max_min(a, 8, lessor, extractor)
    assert ret == 2


class Solution:
    def __init__(self):
        pass

    def count_l_r(self, up_nums, down_nums):
        self.up_nums   = up_nums
        self.down_nums = down_nums

        self.max_pre_count = 0
        self.pre_count = 0
        self.count = 0

        self.up_window   = []       # 单调队列(类似于滑动窗口最大值)
        self.down_window = []       # 单调队列(类似于滑动窗口最大值)


        # for u, d in zip(self.up_nums, self.down_nums):
        #     self.slide_move(u, d)
        for idx in range(len(self.up_nums)):
            self.slide_one_ele(idx)

        print("max_pre_count ", self.max_pre_count)
        return self.count

    def slide_one_ele(self, idx):
        # 计数: 上面最小值, 大于下面最大值
        u, d = self.up_nums[idx], self.down_nums[idx]

        # 这个if判断去掉, 完全由下面通用规则, 也是可以的.
        # pre_count 是妙用
        if d >= u:
            self.reset()
            return

        self.update_up_window(idx)
        self.update_down_window(idx)

        self.calc_count(u, d)

        # print(' pre_count, count', self.pre_count, self.count)
        self.max_pre_count = max(self.max_pre_count, self.pre_count)
        # print(' after in ', idx, self.up_nums[idx], self.down_nums[idx])
        # self.show()

    def show(self):
        for idx in self.up_window:
            print(self.up_nums[idx], sep=", ", end=' ')

        print()
        for idx in self.down_window:
            print(self.down_nums[idx], sep=", ", end=' ')
        print()
        print()

    def calc_count(self, u, d):
        self.hit = False

        if len(self.up_window) == 1:
            # 最小值变了.
            self.calc_by_up(u)
            # print('[ hit up')
        elif len(self.down_window) == 1:
            # 最大值变了
            # print('[ hit down')
            self.calc_by_down(d)

        # print('[ hit no change')
        if not self.hit:
            self.pre_count += 1
            self.count += self.pre_count

    def calc_by_up(self, u):
        # for i in range(len(self.down_window)-1, -1, -1):
        #     down_idx = self.down_window[i]
        #     down_num = self.down_nums[down_idx]
        #     if down_num >= u:
        #         self.hit = True
        #         self.down_window = self.down_window[i+1:]
        #         self.pre_count = self.up_window[-1] - down_idx
        #         self.count += self.pre_count
        #         return
        # self.hit = False

        # HINT: NOTE:用了二分搜索之后, 针对极端情况, 快了很多
        find_idx = self.find_down_bound(u)
        if find_idx == -1:
            self.hit = False
            return
        else:
            self.hit = True
            # print("find_idx", find_idx, len(self.down_window))
            down_idx = self.down_window[find_idx]
            self.down_window = self.down_window[find_idx+1:]
            self.pre_count = self.up_window[-1] - down_idx
            self.count += self.pre_count
            return

    def find_down_bound(self, u):
        def extractor(i):
            return self.down_nums[ self.down_window[i] ]

        def lessor(a, b):
            return a >= b       # 找到最后一个 mid_num >= up的

        return binary_find_max_min(self.down_window, u, lessor, extractor)
        # for i in range(len(self.down_window)-1, -1, -1):
        #     down_idx = self.down_window[i]
        #     down_num = self.down_nums[down_idx]
        #     if down_num >= u:
        #         self.hit = True
        #         self.down_window = self.down_window[i+1:]
        #         self.pre_count = self.up_window[-1] - down_idx
        #         self.count += self.pre_count
        #         return

    def calc_by_down(self, d):
        # for i in range(len(self.up_window)-1, -1, -1):
        #     up_idx = self.up_window[i]
        #     up_num = self.up_nums[up_idx]
        #     if up_num <= d:
        #         self.hit = True
        #         self.up_window = self.up_window[i+1:]
        #         self.pre_count = self.down_window[-1] - up_idx
        #         self.count += self.pre_count
        #         return

        # self.hit = False

        find_idx = self.find_up_bound(d)
        if find_idx == -1:
            self.hit = False
            return
        else:
            self.hit = True
            # print("find_idx", find_idx, len(self.up_window))
            up_idx = self.up_window[find_idx]
            self.up_window = self.up_window[find_idx+1:]
            self.pre_count = self.up_window[-1] - up_idx
            self.count += self.pre_count
            return

    def find_up_bound(self, d):
        def extractor(i):
            return self.up_nums[ self.up_window[i] ]

        def lessor(a, b):
            return a <= b       # 找到最后一个 mid_num <= d 的

        return binary_find_max_min(self.up_window, d, lessor, extractor)

    def update_up_window(self, idx):
        u = self.up_nums[idx]
        while self.up_window:
            most_right_num = self.up_nums[self.up_window[-1]]
            if most_right_num < u:
                break

            self.up_window.pop()

        # 返回前必须调用
        self.up_window.append(idx)

    def update_down_window(self, idx):
        d = self.down_nums[idx]
        while self.down_window:
            most_right_num = self.down_nums[self.down_window[-1]]
            if most_right_num > d:
                break

            self.down_window.pop()

        # 返回前必须调用
        self.down_window.append(idx)


    def reset(self):
        self.up_window.clear()
        self.down_window.clear()

        self.pre_count = 0

class SolutionSimple:
    def __init__(self):
        pass

    def count_l_r(self, up_nums, down_nums):
        self.up_nums   = up_nums
        self.down_nums = down_nums

        self.count = 0

        self.calc()
        return self.count

    def calc(self):
        for idx in range(len(self.up_nums)):
            self.count += self.calc_as_right(idx)

    def calc_as_right(self, idx):
        cur_count = 0
        cur_min = 2**31
        cur_max = -2**31
        for i in range(idx, -1, -1):
            # if self.down_nums[i] >= self.up_nums[i]:
            #     break

            cur_min = min(cur_min, self.up_nums[i])
            cur_max = max(cur_max, self.down_nums[i])
            if cur_max >= cur_min:
                break
            cur_count += 1

        return cur_count

def get_l1_l2():
    n = 100000

    # ------------------- m1 ---------------------
    # l1 = list( range(n) )
    # l2 = list( range(n) )
    # random.shuffle(l1)
    # random.shuffle(l2)

    # ------------------- m2 ---------------------
    # data = range(n)
    # l1 = random.sample(data, 5000)
    # l2 = random.sample(data, 5000)

    # ------------------- m3 ---------------------
    u_start, d_start, span = 500000, 100, 6000
    l1 = list(range(u_start, u_start+span))
    l2 = list(range(d_start, d_start+span))

    return l1, l2


def test():
    s = Solution()

    l1, l2 = get_l1_l2()

    # ret = s.count_l_r([3, 3, 3,], [3, 2, 1])
    # l1 = [6,  3, 10, 8, 4, 9,  5, 1, 13, 7, 11, 14, 12, 0, 2]
    # l2 = [10, 8, 11, 7, 1, 0, 14, 9, 12, 4, 5,  6,  2,  3, 13]
    #            1  3  5   7                       8 10      11  13     14  16
    # l1 = [8,  0, 7, 9, 11, 16, 4,  3,  1, 19, 17, 18, 5, 12, 14, 13, 2, 10, 15,  6]
    # l2 = [16, 8, 1, 0, 5,  9, 15, 18, 14, 19, 17,  7, 3, 13, 12, 10, 6,  4,  2, 11]
    # print(l1)
    # print(l2)
    ret = s.count_l_r(l1, l2)
    print(ret)

    sm = SolutionSimple()
    ret2 = sm.count_l_r(l1, l2)
    print(ret2)

    assert ret == ret2
    # assert ret == sm.count_l_r(l1, l2)

def main():
    print("start main")
    test_binary_s()
    test()

if __name__ == "__main__":
    main()
